package Leetcode第一期;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : K k
 * @date : 17:41 2020/9/10
 * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
 *
 * 示例 1:
 *
 * 输入: 1->1->2
 * 输出: 1->2
 * 示例 2:
 *
 * 输入: 1->1->2->3->3
 * 输出: 1->2->3
 */
public class 删除排序链表中的重复元素_83 {

    //通解，hashmap去重，适用于所有链表，本题题意是排序后的链表
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return head;
        ListNode pre=head;
        ListNode cur=head.next;
        Map<Integer,ListNode> map=new HashMap<>();
        map.put(head.val,head);
        while(cur!=null){
            if(map.containsKey(cur.val)){
                //若存在该节点，进行删除
                pre.next=cur.next;
                cur.next=null;
                cur=pre.next;
            }else{
                //若map中不存在该节点 则添加进map
                map.put(cur.val,cur);
                pre=cur;
                cur=cur.next;
            }
        }
        return head;
    }

    //双指针
    public ListNode deleteDuplicatesA(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;
        while (cur!=null){
            if (pre!=null){
                if (pre.val==cur.val){
                    pre.next=cur.next;
                    cur.next=null;
                    cur=pre.next;
                }else {
                    pre=cur;
                    cur=cur.next;
                }
            }else {
                pre=cur;
                cur=cur.next;
            }
        }
        return head;
    }
}
